package cc.lucien.demo02.homework;

import cc.lucien.demo02.ArrayGenerator;
import cc.lucien.demo02.SortingHelper;

/**
 * 换个角度实现插入排序，从后开始排序
 */
public class InsertionSort {
    public static <E extends Comparable<E>> void sort(E[] arr){
        for (int i = arr.length - 1; i >= 0; i--) {
            E temp = arr[i];
            int j;
            for (j = i; j + 1 < arr.length; j++) {
                if (temp.compareTo(arr[j+1]) > 0)
                    arr[j] = arr[j+1];
                else
                    break;
            }
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] data = {10000, 100000};
        for (int n : data){
            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
            long startTime = System.nanoTime();
            sort(arr);
            long endTime = System.nanoTime();
            if (SortingHelper.isSorted(arr)){
                double time = (endTime - startTime) / 1000000000.0;
                System.out.println(String.format("InsertionSort, n = %d : %f s",n,time));
            }
        }
    }
}
